Lương Sư Đô liên kết với một thủ lĩnh nổi dậy Quách Tử Hòa (郭子和) ở phía bắc, Quách Tử Hòa cũng dựa vào Đông Đột Quyết.[2] Năm 618, tướng Lý Uyên phản lại Tùy Dạng Đế và tiến vào kinh thành Trường An. một thủ lĩnh nổi dậy khác là Tần Đế Tiết Cử nghe theo lời của Hác Viện mà liên binh với Lương Sư Đô và Đông Đột Quyết, tìm cách tiến công Trường An. Tuy nhiên, Lý Uyên thuyết phục được tướng Đông Đột Quyết là A Sử Na Đốt Bật từ bỏ chiến dịch. Lý Uyên buộc Tùy Cung Đế Dương Hựu thiện nhượng cho mình, lập ra triều Đường. Đến ngày Đinh Mùi (4) tháng 7 (31 tháng 7), Lương Sư Đô tiến công Linh châu[c 7]-một châu đã quy phục Đường- song bị Phiêu kị tướng quân Lận Hưng Xán đánh bại.[3]

Vào mùa xuân năm 619, Đường Cao Tổ khiển Hiếu Mô An tiến công vào biên giới của Lương Sư Đô, song bị Lương Sư Đô bắt được rồi giết do bị người này mắng chửi. Thủy Tấy khả hãn lên kế hoạch đại tiến công vào Trung Nguyên, cả Lương Sư Đô và Định Dương khả hãn Lưu Vũ Chu (một thủ lĩnh nổi dậy khác) đều tham gia cùng với Đông Đột Quyết khả hãn. Tuy nhiên, Thủy Tất khả hãn lại từ trần, A Sử Na Sĩ Lợi Phất Thiết trở thành khả hãn kế vị (tức Xử La khả hãn) và đã từ bỏ chiến dịch sau khi nhận được tặng phẩm lớn từ Đường. Sau đó, ngày Canh Ngọ (1) tháng 3 (20 tháng 4), Lương Sư Đô tiếp tục tiến công Linh châu, song bị Trưởng sử Dương Tắc đánh đuổi. Đến tháng 8 ÂL, Lương Sư Đô cùng Đông Đột Quyết đem mấy nghìn quân tấn công Diên châu (延州, tức Diên An quận trước đó), tướng Đường là Hành quân tổng quản Đoàn Đức Thao (段德操) thấy mình có ít binh sĩ nên bế bích bất chiến, dò xét quân địch. Đến ngày Bính Dần (1) tháng 9 (13 tháng 10), Đoàn Đức Thao khiển Phó tổng quản Lương Lễ đem binh tiến công, giao chiến với Lương Sư Đô. Đoàn Đức Thao dẫn khinh kỵ giương nhiều cờ hiệu, yểm kích phía sau, quân của Lương Sư Đô tan vỡ, chạy 200 dặm về phía bắc. Đoàn Đức Thao cho quân đánh Ngụy châu, bắt hơn hai nghìn khẩu. Ngày Ất Mùi (30) tháng 9 (11 tháng 11), Lương Sư Đô lại tiến công Diên châu, song lại chiến bại trước Đoàn Đức Thao, hơn hai nghìn quân Lương bị giết, Lương Sư Đô cùng hơn một trăm kị binh rút về.[4] Tháng 7 năm Canh Thìn (620), Lương Sư Đô dẫn quân Đột Quyết, Kê Hồ tiến công, song lại bị Đoàn Đức Thao đánh bại, hơn một nghìn quân bị giết.[5]

Trong khi đó, Quách Tử Hòa quay sang quy phục triều Đường và chống lại Lương Sư Đô và Đông Đột Quyết, đoạt lấy thành Ninh Sóc[c 8] từ Lương Sư Đô. Ngày Quý Mão tháng 8 (14 tháng 9), tướng lưu thủ Thạch Bảo thành của Lương Sư Đô là Trương Cử (張舉) đem hơn một nghìn người đầu hàng triều Đường. Ngày Canh Ngọ (10) tháng 9 (11 tháng 10), tướng Lưu Mân (劉旻) đem Hoa Trì hàng Đường. Trong khi đó Lưu Vũ Chu bị Đường đánh bại vào đầu năm, Lương Sư Đô rất lo sợ nên khiển Thượng thư Lục Quý Lãm (陸季覽) đến thuyết phục Xử La khả hãn chống lại Đường trước khi Đường trở nên quá mạnh. Xử La khả hãn đồng ý, và lập một kế hoạch tổng tiến công Đường, liên kết với quân Hề, Khiết Đan, Mạt Hạt và Hạ Vương Đậu Kiến Đức (một thủ lĩnh nổi dậy khác). Tuy nhiên, Xử La khả hãn từ trần trước khi thực hiện kế hoạch, A Sử Na Đốt Bật kế vị (tức Hiệt Lợi khả hãn).[5] Tháng 3 năm Tân Tị (621), một người Kê Hồ là Lưu Hiên Thành (劉屳成) phản lại triều Đường, chạy sang với Lương Sư Đô.[6] Sau đó, Lương Sư Đô tin vào sàm ngôn mà giết Lưu Hiên Thành, do vậy thuộc hạ rất lo sợ, nhiều người đi hàng triều Đường.[7]

Ngày Canh Thìn tháng 2 năm Nhâm Ngọ (14 tháng 4 năm 622), Đoàn Đức Thao đem quân đến đánh Thạch Bảo thành của Lương Sư Đô. Lương Sư Đô tự đemq uân đến cứu, kết quả Lương Sư Đô chiến bại trước Đoàn Đức Thao và chạy về cùng 16 kị binh. Đường Cao Tổ tăng thêm quân cho Đoàn Đức Thao, sai thừa thắng tấn công Hạ châu, chiếm được Đông thành của kinh đô Sóc Phương, Lương Sư Đô và vài trăm người buộc phải thoát lui vào bảo vệ Tây thành. Tuy nhiên, Lương Sư Đô cầu cứu Đông Đột Quyết, Đường Cao Tổ hạ chiếu cho Đoàn Đức Thao triệt thoái khi biết tin quân Đông Đột Quyết đến. Sau đó, Lương Sư Đô phái đệ là Lương Lạc nhi (梁洛兒) suất quân cùng với Đông Đột Quyết tiến công Linh châu của Đường, song bị tướng Đường là Lý Đạo Tông đẩy lui.[8]